package pro.softzhang.algo.lc100;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * 100. 相同的树
 * https://leetcode.cn/problems/same-tree/description/
 */
public class LC100_SameTree {

    public static void main(String[] args) {
        TreeNode tree1 = new TreeNode(1, new TreeNode(2), null);
        TreeNode tree2 = new TreeNode(1, null, new TreeNode(3));
        System.out.println(new Solution1().isSameTree(tree1, tree2));
    }


    /**
     * 自己写的，应该还可以优化
     */
    static
    class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null && q == null) {
                return true;
            }

            if (p == null || q == null) {
                return false;
            }

            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right) && p.val == q.val;
        }
    }

    /**
     *
     */
    @XOptimal
    static
    class Solution1 {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            // 如果有1个节点为null
            if (p == null || q == null) {
               return p == q;
            }

            // 必须val相同且结果相同，这样可以减少递归层数
            return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}
